package xyz.ibenben.zhongdian.common.util.example.easy;

/**
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 * 如果不存在公共前缀，返回空字符串 ""。
 * <p>
 * 示例 1:
 * 输入: ["flower","flow","flight"]
 * 输出: "fl"
 * 示例 2:
 * 输入: ["dog","racecar","car"]
 * 输出: ""
 * 解释: 输入不存在公共前缀。
 * 说明:
 * <p>
 * 所有输入只包含小写字母 a-z 。
 */
public class LongestPrefix {
    public static void main(String[] args) {
        LongestPrefix lp = new LongestPrefix();
        String[] arg = {"aa", "aaa"};
        System.out.println(lp.longestCommonPrefix(arg));
        System.out.println(lp.longestCommonPrefix2(arg));
    }

    /**
     * 我给出的解决方案
     *
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {
        StringBuilder result = new StringBuilder();
        if (strs.length > 0 && strs[0].length() > 0) {
            for (int i = 0; i < strs[0].length(); i++) {
                boolean add = true;
                for (int j = 1; j < strs.length; j++) {
                    if (strs[j].length() <= i) {
                        add = false;
                        break;
                    }
                    if (strs[0].charAt(i) != strs[j].charAt(i)) {
                        return result.toString();
                    }
                }
                if (add) {
                    result.append(strs[0].charAt(i));
                }
            }
        }
        return result.toString();
    }

    /**
     * 官方给出的解决方案
     *
     * @param strs
     * @return
     */
    public String longestCommonPrefix2(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) {
                    return "";
                }
            }
        }
        return prefix;
    }
}
